{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Number of Increasing Paths in a Grid"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #depth-first-search #breadth-first-search #graph #topological-sort #memoization #array #dynamic-programming #matrix"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #深度优先搜索 #广度优先搜索 #图 #拓扑排序 #记忆化搜索 #数组 #动态规划 #矩阵"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countPaths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #网格图中递增路径的数目"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个&nbsp;<code>m x n</code>&nbsp;的整数网格图&nbsp;<code>grid</code>&nbsp;，你可以从一个格子移动到&nbsp;<code>4</code>&nbsp;个方向相邻的任意一个格子。</p>\n",
    "\n",
    "<p>请你返回在网格图中从 <strong>任意</strong>&nbsp;格子出发，达到 <strong>任意</strong>&nbsp;格子，且路径中的数字是 <strong>严格递增</strong>&nbsp;的路径数目。由于答案可能会很大，请将结果对&nbsp;<code>10<sup>9</sup> + 7</code>&nbsp;<strong>取余</strong>&nbsp;后返回。</p>\n",
    "\n",
    "<p>如果两条路径中访问过的格子不是完全相同的，那么它们视为两条不同的路径。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2022/05/10/griddrawio-4.png\" style=\"width: 181px; height: 121px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>grid = [[1,1],[3,4]]\n",
    "<b>输出：</b>8\n",
    "<b>解释：</b>严格递增路径包括：\n",
    "- 长度为 1 的路径：[1]，[1]，[3]，[4] 。\n",
    "- 长度为 2 的路径：[1 -&gt; 3]，[1 -&gt; 4]，[3 -&gt; 4] 。\n",
    "- 长度为 3 的路径：[1 -&gt; 3 -&gt; 4] 。\n",
    "路径数目为 4 + 3 + 1 = 8 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre><b>输入：</b>grid = [[1],[2]]\n",
    "<b>输出：</b>3\n",
    "<b>解释：</b>严格递增路径包括：\n",
    "- 长度为 1 的路径：[1]，[2] 。\n",
    "- 长度为 2 的路径：[1 -&gt; 2] 。\n",
    "路径数目为 2 + 1 = 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= grid[i][j] &lt;= 10<sup>5</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [number-of-increasing-paths-in-a-grid](https://leetcode.cn/problems/number-of-increasing-paths-in-a-grid/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [number-of-increasing-paths-in-a-grid](https://leetcode.cn/problems/number-of-increasing-paths-in-a-grid/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,1],[3,4]]', '[[1],[2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        values = []\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                values.append((grid[i][j], i, j))\n",
    "        values.sort(reverse=True) \n",
    "        dp = [[1]*n for _ in range(m)]\n",
    "        ans = 0\n",
    "        for val, i, j in values:\n",
    "            for dx, dy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:\n",
    "                ni = i + dx\n",
    "                nj = j + dy\n",
    "                if m > ni >= 0 and n > nj >= 0 and val < grid[ni][nj]:\n",
    "                    dp[i][j] = (dp[i][j] + dp[ni][nj]) % MOD\n",
    "            ans = (ans + dp[i][j]) % MOD\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        # 初始化 DP 表\n",
    "        dp = [[0] * n for _ in range(m)]\n",
    "        \n",
    "        # 按值排序的 (x, y) 坐标列表\n",
    "        cells = [(x, y) for x in range(m) for y in range(n)]\n",
    "        cells.sort(key=lambda xy: grid[xy[0]][xy[1]])\n",
    "        \n",
    "        for x, y in cells:\n",
    "            dp[x][y] = 1  # 至少有一条从自身到自身的路径\n",
    "            for dx, dy in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] < grid[x][y]:\n",
    "                    dp[x][y] += dp[nx][ny]\n",
    "                    \n",
    "            dp[x][y] %= MOD\n",
    "        \n",
    "        return sum(sum(row) for row in dp) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        n,m = len(grid),len(grid[0])\n",
    "        def count(i,j):\n",
    "            up = down = left = right = 0\n",
    "            if i - 1 >= 0 and grid[i][j] > grid[i-1][j]:\n",
    "                left = record[i-1][j] if record[i-1][j]!=0 else count(i-1,j)\n",
    "            if j - 1 >= 0 and grid[i][j] > grid[i][j-1]:\n",
    "                up = record[i][j-1] if record[i][j-1] != 0 else count(i, j-1)\n",
    "            if i + 1 < n and grid[i][j] > grid[i+1][j]:\n",
    "                right = record[i+1][j] if record[i+1][j]!=0 else count(i+1,j)\n",
    "            if j + 1 < m and grid[i][j] > grid[i][j+1]:\n",
    "                down = record[i][j+1] if record[i][j+1]!=0 else count(i,j+1)\n",
    "\n",
    "            res = (1 + up + down + left + right) % mod\n",
    "            record[i][j] = res\n",
    "            return res\n",
    "\n",
    "        mod = 10**9+7\n",
    "        record = [[0 for _ in range(m)] for __ in range(n)]\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                if record[i][j] == 0:  # 递归过程会计算其他点，尚未探索的点才进行寻找\n",
    "                    count(i, j)\n",
    "\n",
    "        return sum([sum(r) for r in record]) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        MOD = 10**9+7\n",
    "        r,c=len(grid),len(grid[0])\n",
    "        self.rec = [[0]*c for _ in range(r)]\n",
    "\n",
    "        def travel(x,y):\n",
    "            if self.rec[x][y] != 0:\n",
    "                return self.rec[x][y]\n",
    "            total = 1\n",
    "            dx = [1,-1,0,0]\n",
    "            dy = [0,0,1,-1]\n",
    "            for i in range(4):\n",
    "                nx,ny = x+dx[i],y+dy[i]\n",
    "                if 0<=nx<r and 0<=ny<c and grid[nx][ny]>grid[x][y]:\n",
    "                    total = total +  travel(nx, ny)\n",
    "            total%=MOD\n",
    "            self.rec[x][y] = total\n",
    "            return total\n",
    "\n",
    "        res = 0\n",
    "        for i in range(r):\n",
    "            for j in range(c):\n",
    "                res +=travel(i,j)\n",
    "        return res%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        f = [[-1] * n for _ in range(m)]\n",
    "\n",
    "        def next_iter(r, c):\n",
    "            for xx, yy in [[1, 0], [-1, 0], [0, 1], [0, -1]]:\n",
    "                nx = r + xx\n",
    "                ny = c + yy\n",
    "                if 0 <= nx < m and 0 <= ny < n:\n",
    "                    yield nx, ny\n",
    "        \n",
    "        def dfs(i, j):\n",
    "            if f[i][j] != -1:\n",
    "                return f[i][j]\n",
    "            mm = 1\n",
    "            for nx, ny in next_iter(i, j):\n",
    "                if grid[i][j] < grid[nx][ny]:\n",
    "                    mm += dfs(nx, ny)\n",
    "            f[i][j] = int(mm % (1e9 + 7))\n",
    "            return f[i][j]\n",
    "\n",
    "        return sum([dfs(i, j) for i in range(m) for j in range(n)]) % (10 ** 9 + 7)\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        directions = [[-1, 0], (0, -1), (1,0), (0, 1)]\n",
    "        MOD = 10**9+7\n",
    "        memo = [[-1]*n for _ in range(m)]\n",
    "        def dfs(x, y):\n",
    "            if memo[x][y]!=-1:\n",
    "                return memo[x][y]\n",
    "            res = 1\n",
    "            for dx, dy in directions:\n",
    "                nx, ny = x+dx, y+dy\n",
    "                if 0<=nx<m and 0<=ny<n and grid[nx][ny]>grid[x][y]:\n",
    "                    res += dfs(nx, ny)\n",
    "            res = res%MOD\n",
    "            memo[x][y] = res\n",
    "            return res\n",
    "        return sum(dfs(i, j) for i in range(m) for j in range(n)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def count(self, i, j):\n",
    "        if i*self.n+j in self.d:\n",
    "            return self.d[i*self.n+j]\n",
    "\n",
    "        r = (1 + (self.count(i-1, j) if i-1>=0 and self.grid[i-1][j]>self.grid[i][j] else 0) % 1000000007 + (self.count(i+1, j) if i+1<self.m and self.grid[i+1][j]>self.grid[i][j] else 0) % 1000000007 + (self.count(i, j-1) if j-1>=0 and self.grid[i][j-1]>self.grid[i][j] else 0) % 1000000007 + (self.count(i, j+1) if j+1<self.n and self.grid[i][j+1]>self.grid[i][j] else 0) % 1000000007) % 1000000007\n",
    "\n",
    "        if r > 1:\n",
    "            self.d[i*self.n+j] = r\n",
    "        return r\n",
    "\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        self.m = m = len(grid)\n",
    "        self.n = n = len(grid[0])\n",
    "        self.grid = grid\n",
    "        self.d = {}\n",
    "        \n",
    "        return sum([self.count(i, j) % 1000000007 for i in range(m) for j in range(n)]) % 1000000007\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        my_dict=collections.defaultdict(list)\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                my_dict[grid[i][j]].append((i,j))\n",
    "        \n",
    "        my_mat=[[1]*len(grid[0]) for i in range(len(grid))]\n",
    "\n",
    "        key_list=list(my_dict.keys())\n",
    "        key_list.sort()\n",
    "        for i in range(1,len(key_list)):\n",
    "            nowv=key_list[i]\n",
    "            for (u,v) in my_dict[nowv]:\n",
    "                for u1,v1 in [(u-1,v),(u+1,v),(u,v-1),(u,v+1)]:\n",
    "                    if 0<=u1<len(grid) and 0<=v1<len(grid[0]) and grid[u1][v1]<grid[u][v]:\n",
    "                        my_mat[u][v]+=my_mat[u1][v1]\n",
    "                        my_mat[u][v]=my_mat[u][v]%(10**9+7)\n",
    "\n",
    "        result=0\n",
    "        for i in range(len(my_mat)):\n",
    "            for j in range(len(my_mat[0])):\n",
    "                result=(result+my_mat[i][j])%(10**9+7)\n",
    "\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        M = 10**9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        d = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                d[grid[i][j]].append((i,j))\n",
    "        \n",
    "        ans = 0\n",
    "        f = [[0]*n for _ in range(m)]\n",
    "        for v in sorted(d):\n",
    "            for i,j in d[v]:\n",
    "                for a,b in [(i-1,j),(i+1,j),(i,j-1),(i,j+1)]:\n",
    "                    if 0 <= a < m and 0 <= b < n and grid[a][b] < v:\n",
    "                        f[i][j] += f[a][b]\n",
    "                f[i][j] += 1\n",
    "                f[i][j] %= M\n",
    "                ans += f[i][j]\n",
    "                ans %= M\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        M = 10**9+7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        posByV = defaultdict(list)\n",
    "        for r, row in enumerate(grid):\n",
    "            for c, v in enumerate(row):\n",
    "                posByV[v].append((r, c))\n",
    "        state = [[1]*n for _ in range(m)]\n",
    "        sortedKeys = sorted(posByV.keys())\n",
    "        res = len(posByV[sortedKeys[0]])\n",
    "        for r, c in chain.from_iterable((posByV[k] for k in sortedKeys[1:])):\n",
    "            state[r][c] = (state[r][c] + sum(state[nr][nc] for nr, nc in [(r, c-1), (r, c+1), (r-1,c), (r+1, c)] if 0<=nr<m and 0<=nc<n and grid[nr][nc] < grid[r][c])) % M\n",
    "            res = (res + state[r][c]) % M\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import collections\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        my_dict=collections.defaultdict(list)\n",
    "        for i in range(len(grid)):\n",
    "            for j in range(len(grid[0])):\n",
    "                my_dict[grid[i][j]].append((i,j))\n",
    "        \n",
    "        my_mat=[[1]*len(grid[0]) for i in range(len(grid))]\n",
    "\n",
    "        result=0\n",
    "        key_list=list(my_dict.keys())\n",
    "        key_list.sort()\n",
    "        for i in range(len(key_list)):\n",
    "            nowv=key_list[i]\n",
    "            for (u,v) in my_dict[nowv]:\n",
    "                for u1,v1 in [(u-1,v),(u+1,v),(u,v-1),(u,v+1)]:\n",
    "                    if 0<=u1<len(grid) and 0<=v1<len(grid[0]) and grid[u1][v1]<grid[u][v]:\n",
    "                        my_mat[u][v]+=my_mat[u1][v1]\n",
    "                        my_mat[u][v]=my_mat[u][v]%(10**9+7)\n",
    "\n",
    "                result=(result+my_mat[u][v])%(10**9+7)\n",
    "\n",
    "        # result=0\n",
    "        # for i in range(len(my_mat)):\n",
    "        #     for j in range(len(my_mat[0])):\n",
    "        #         result=(result+my_mat[i][j])%(10**9+7)\n",
    "\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "DIRS = {(1, 0), (0, 1), (-1, 0), (0, -1)}\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        # 建立有向图\n",
    "        graph = defaultdict(list)\n",
    "        indeg = [0] * m * n\n",
    "\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                u = x * n + y\n",
    "                for dx, dy in DIRS:\n",
    "                    nx, ny = x + dx, y + dy\n",
    "                    if (0 <= nx < m and \n",
    "                        0 <= ny < n and \n",
    "                        grid[x][y] < grid[nx][ny]):\n",
    "                        v = nx * n + ny\n",
    "\n",
    "                        # grid[x][y] < grid[nx][ny]\n",
    "                        # [x, y] -> [nx, ny]\n",
    "                        graph[u].append(v)\n",
    "                        indeg[v] += 1\n",
    "        \n",
    "        # 拓扑序DP\n",
    "        # dp[u]: 以结点 u([u // n, u % n]) 为结尾的严格递增路径的个数\n",
    "        # 初始化：dp[u] = 1\n",
    "        # 转移方程：dp[v] = sum(dp[u]) + 1, (u, v)\n",
    "        # 目标：sum(dp)\n",
    "        dp = [1] * m * n\n",
    "\n",
    "        que = deque()\n",
    "        for x in range(m):\n",
    "            for y in range(n):\n",
    "                u = x * n + y\n",
    "                if indeg[u] == 0:\n",
    "                    que.append(u)\n",
    "        \n",
    "        while que:\n",
    "            u = que.popleft()\n",
    "\n",
    "            for v in graph[u]:\n",
    "                dp[v] = (dp[v] + dp[u]) % MOD\n",
    "                \n",
    "                indeg[v] -= 1\n",
    "                if indeg[v] == 0:\n",
    "                    que.append(v)\n",
    "        \n",
    "        return sum(dp) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "direction = [-1, 0, 1, 0, -1]\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y):\n",
    "            res = 1\n",
    "            for dx, dy in pairwise(direction):\n",
    "                a, b = x + dx, y + dy\n",
    "                if 0 <= a < m and 0 <= b < n and grid[a][b] < grid[x][y]:\n",
    "                    res += dfs(a, b)\n",
    "                    res %= kmod\n",
    "            return res\n",
    "        \n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans += dfs(i, j)\n",
    "                ans %= kmod\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        move = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        d = [[0]*n for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for dx,dy in move:\n",
    "                    x,y = i+dx,j+dy\n",
    "                    if x<0 or y<0 or x>=m or y>=n: continue\n",
    "                    if grid[x][y] < grid[i][j]: d[i][j] += 1\n",
    "        s = [[1]*n for _ in range(m)]\n",
    "        q = [(i,j) for i in range(m) for j in range(n) if d[i][j]==0]\n",
    "        while q:\n",
    "            i,j = q.pop()\n",
    "            for dx,dy in move:\n",
    "                x,y = i+dx,j+dy\n",
    "                if x<0 or y<0 or x>=m or y>=n: continue\n",
    "                if grid[x][y] > grid[i][j]:\n",
    "                    s[x][y] += s[i][j]\n",
    "                    d[x][y] -= 1\n",
    "                    if d[x][y] == 0: q.append((x,y))\n",
    "        # for l in s: print(l)\n",
    "        return sum(map(sum,s))%1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def make_graph(self, grid):\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        graph = defaultdict(list)\n",
    "        indeg = defaultdict(int)\n",
    "        x_dirs = [0, 0, 1, -1]\n",
    "        y_dirs = [1, -1, 0, 0]\n",
    "        for row in range(n):\n",
    "            for col in range(m):\n",
    "                for x_dir, y_dir in zip(x_dirs, y_dirs):\n",
    "                    n_row = row + x_dir\n",
    "                    n_col = col + y_dir\n",
    "                    if 0 <= n_row < n and 0 <= n_col < m and grid[n_row][n_col] > grid[row][col]:\n",
    "                        graph[(row, col)].append((n_row, n_col))\n",
    "                        indeg[(n_row, n_col)] += 1\n",
    "        return graph, indeg\n",
    "\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        # grid strictly increasing -> DAG\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        graph, indeg = self.make_graph(grid)\n",
    "        dp = [[1] * m for _ in range(n)]\n",
    "        queue = collections.deque([])\n",
    "        MOD = 10**9 + 7\n",
    "        for row in range(n):\n",
    "            for col in range(m):\n",
    "                if indeg[(row, col)] == 0:\n",
    "                    queue.append((row, col))\n",
    "        \n",
    "        x_dirs = [0, 0, 1, -1]\n",
    "        y_dirs = [1, -1, 0, 0]\n",
    "\n",
    "        while queue:\n",
    "            (row, col) = queue.popleft()\n",
    "            for n_row, n_col in graph[(row, col)]:\n",
    "                dp[n_row][n_col] = (dp[n_row][n_col] + dp[row][col]) % MOD\n",
    "                indeg[(n_row, n_col)] -= 1\n",
    "                if indeg[(n_row, n_col)] == 0:\n",
    "                    queue.append((n_row, n_col))\n",
    "        \n",
    "        res = 0\n",
    "        for row in range(n):\n",
    "            for col in range(m):\n",
    "                res = (res + dp[row][col]) % MOD\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        g = [[] for _ in range(m * n)]\n",
    "        deg = [0] * (m * n)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for x, y in ((i+1, j), (i-1, j), (i, j+1), (i, j-1)):\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[i][j] < grid[x][y]:\n",
    "                        g[i*n+j].append(x*n+y)\n",
    "                        deg[x*n+y] += 1\n",
    "        \n",
    "        nodes = [0] * (m * n)\n",
    "        queue = deque()\n",
    "        for idx, i in enumerate(deg):\n",
    "            if i == 0:\n",
    "                queue.append(idx)\n",
    "                nodes[idx] = 1\n",
    "        \n",
    "        ans = m * n\n",
    "        while queue:\n",
    "            node = queue.popleft()\n",
    "            for i in g[node]:\n",
    "                deg[i] -= 1\n",
    "                nodes[i] += nodes[node]\n",
    "                if deg[i] == 0:\n",
    "                    queue.append(i)\n",
    "                    ans += nodes[i]\n",
    "                    nodes[i] += 1\n",
    "        \n",
    "        return ans % int(10**9 + 7)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "DIRS = {(1, 0), (0, 1), (-1, 0), (0, -1)}\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        indeg = [0] * m * n\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        que = deque()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                que.append((i, j))\n",
    "                while que:\n",
    "                    x, y = que.popleft()\n",
    "                    for dx, dy in DIRS:\n",
    "                        nx, ny = x + dx, y + dy\n",
    "                        if (0 <= nx < m and \n",
    "                            0 <= ny < n and \n",
    "                            grid[nx][ny] > grid[x][y]):\n",
    "                            graph[x * n + y].append(nx * n + ny)\n",
    "                            indeg[nx * n + ny] += 1\n",
    "        \n",
    "        que.extend(x * n + y \n",
    "            for x in range(m) \n",
    "            for y in range(n) \n",
    "            if indeg[x * n + y] == 0\n",
    "        ) \n",
    "\n",
    "        dp = [1] * m * n\n",
    "\n",
    "        while que:\n",
    "            u = que.popleft()\n",
    "\n",
    "            for v in graph[u]:\n",
    "                dp[v] += dp[u]\n",
    "                \n",
    "                indeg[v] -= 1\n",
    "                if indeg[v] == 0:\n",
    "                    que.append(v)\n",
    "        \n",
    "        return sum(dp) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "DIRS = {(1, 0), (0, 1), (-1, 0), (0, -1)}\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        indeg = [0] * m * n\n",
    "        graph = defaultdict(list)\n",
    "\n",
    "        que = deque()\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                que.append((i, j))\n",
    "\n",
    "                while que:\n",
    "                    x, y = que.popleft()\n",
    "                    u = x * n + y\n",
    "\n",
    "                    for dx, dy in DIRS:\n",
    "                        nx, ny = x + dx, y + dy\n",
    "                        v = nx * n + ny\n",
    "\n",
    "                        if (0 <= nx < m and \n",
    "                            0 <= ny < n and \n",
    "                            grid[nx][ny] > grid[x][y]):\n",
    "\n",
    "                            graph[u].append(v)\n",
    "                            indeg[v] += 1\n",
    "        \n",
    "        que.extend(x * n + y \n",
    "            for x in range(m) \n",
    "            for y in range(n) \n",
    "            if indeg[x * n + y] == 0\n",
    "        ) \n",
    "\n",
    "        dp = [1] * m * n\n",
    "\n",
    "        while que:\n",
    "            u = que.popleft()\n",
    "\n",
    "            for v in graph[u]:\n",
    "                dp[v] += dp[u]\n",
    "                \n",
    "                indeg[v] -= 1\n",
    "                if indeg[v] == 0:\n",
    "                    que.append(v)\n",
    "        \n",
    "        return sum(dp) % MOD\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        outdeg = [[0]*n for _ in range(m)]\n",
    "        dp = [[1]*n for _ in range(m)]\n",
    "        dic = defaultdict(list)\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for x, y in [(i+1, j), (i-1, j), (i, j+1), (i, j-1)]:\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y] > grid[i][j]:\n",
    "                        outdeg[i][j] += 1\n",
    "                        dic[(x, y)].append((i, j))\n",
    "        \n",
    "        q = deque([])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if not outdeg[i][j]:\n",
    "                    q.append((i, j))\n",
    "        \n",
    "        while q:\n",
    "            x, y = q.popleft()\n",
    "            for nx, ny in dic[(x, y)]:\n",
    "                dp[nx][ny] += dp[x][y]\n",
    "                outdeg[nx][ny] -= 1\n",
    "                if not outdeg[nx][ny]:\n",
    "                    q.append((nx, ny))\n",
    "        \n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            res += sum(dp[i])\n",
    "        return res % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            res = 1\n",
    "            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] > grid[i][j]:\n",
    "                    res += dfs(x, y)\n",
    "            return res % MOD\n",
    "        return sum(dfs(i, j) for i in range(m) for j in range(n)) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        \n",
    "        mod = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        @cache\n",
    "        def dfs(i:int, j:int)->int:\n",
    "            res = 1\n",
    "            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                if 0 <= x < m and 0 <=y < n and grid[x][y] > grid[i][j]:\n",
    "                    res += dfs(x, y)\n",
    "            return res % mod\n",
    "        return sum(dfs(i, j) for i in range(m) for j in range(n)) % mod\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            res = 1\n",
    "            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] > grid[i][j]:\n",
    "                    res += dfs(x, y)\n",
    "            return res % MOD\n",
    "        return sum(dfs(i, j) for i in range(m) for j in range(n)) % MOD\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mod = 10 ** 9 + 7\n",
    "\n",
    "        @cache\n",
    "        def dfs(x, y):\n",
    "            \n",
    "            res = 1\n",
    "            for nx, ny in (x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1):\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > grid[x][y]:\n",
    "                    res += dfs(nx, ny)\n",
    "\n",
    "            return res % mod\n",
    "\n",
    "        return sum(dfs(i, j) for i in range(m) for j in range(n)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            res = 1\n",
    "            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] > grid[i][j]:\n",
    "                    res += dfs(x, y)\n",
    "            return res % MOD\n",
    "        return sum(dfs(i, j) for i in range(m) for j in range(n)) % MOD\n",
    " "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\r\n",
    "        MOD = 10 ** 9 + 7\r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "        @cache\r\n",
    "        def dfs(i: int, j: int) -> int:\r\n",
    "            res = 1\r\n",
    "            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\r\n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] > grid[i][j]:\r\n",
    "                    res += dfs(x, y)\r\n",
    "            return res % MOD\r\n",
    "        return sum(dfs(i, j) for i in range(m) for j in range(n)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        mod=10**9+7\n",
    "        @cache\n",
    "        def dfs(i:int,j:int)->int:\n",
    "            ans=1\n",
    "            for x,y in (i+1,j),(i,j+1),(i-1,j),(i,j-1):\n",
    "                if 0<=x<m and 0<=y<n and grid[x][y]>grid[i][j]:\n",
    "                    ans=(ans+dfs(x,y))%mod\n",
    "            return ans\n",
    "        return sum(dfs(i,j) for i in range(m) for j in range(n))%mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            res = 1\n",
    "            for x, y in [[i + 1, j], [i - 1, j], [i, j + 1], [i, j - 1]]:\n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] > grid[i][j]:\n",
    "                    res += dfs(x, y)\n",
    "            return res % mod\n",
    "        res = 0\n",
    "        mod = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res += dfs(i, j)\n",
    "        return res % mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            res = 1\n",
    "            for x, y in (i+1, j), (i, j+1), (i-1, j), (i, j-1):\n",
    "                if 0<= x < m and 0 <= y < n and grid[x][y] > grid[i][j]:\n",
    "                    res += dfs(x, y)\n",
    "            return res % MOD\n",
    "        return sum(dfs(i, j) for i in range(m) for j in range(n)) % MOD\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            res = 1\n",
    "            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] >grid[i][j]:\n",
    "                    res += dfs(x, y)\n",
    "            return res % mod\n",
    "        return sum(dfs(i, j) for i in range(m) for j in range(n)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            res = 1\n",
    "            for x, y in (i+1, j), (i-1, j), (i, j+1), (i, j-1):\n",
    "                if 0 <= x < row and 0 <= y < col and grid[x][y] > grid[i][j]:\n",
    "                    res += dfs(x, y)\n",
    "            return res % MOD\n",
    "\n",
    "        return sum(dfs(i, j) for i in range(row) for j in range(col)) % MOD  \n",
    "        \n",
    "\n",
    "\n",
    "                        \n",
    "\n",
    "\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        mod = 10**9 + 7\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            res = 1\n",
    "            for x, y in [[i-1, j], [i+1, j], [i, j-1], [i, j+1]]:\n",
    "                if 0<=x<m and 0<=y<n and grid[x][y] > grid[i][j]:\n",
    "                    res += dfs(x, y)\n",
    "            return res % mod\n",
    "        \n",
    "        ans = sum(sum(dfs(i, j) for j in range(n))%mod for i in range(m))\n",
    "        return ans % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        @cache\n",
    "        def dfs(i: int, j: int) -> int:\n",
    "            res = 1\n",
    "            for x, y in (i + 1, j), (i - 1, j), (i, j + 1), (i, j - 1):\n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] >grid[i][j]:\n",
    "                    res += dfs(x, y)\n",
    "            return res % mod\n",
    "        return sum(dfs(i, j) for i in range(m) for j in range(n)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        f = lambda x: x % (10 ** 9 + 7)\n",
    "\n",
    "        @cache\n",
    "        def dfs(r: int, c: int) -> int:\n",
    "            ret = 1\n",
    "            directions = ((r + 1, c), (r - 1, c), (r, c + 1), (r, c - 1))\n",
    "            for x, y in directions:\n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] > grid[r][c]:\n",
    "                    ret += dfs(x, y)\n",
    "            return f(ret)\n",
    "        \n",
    "        return f(sum(dfs(r, c) for r in range(m) for c in range(n)))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        # dp[i][j] 是以第 i 行第 j 列格子为起点的路径数\n",
    "        mod = 10**9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            res = 1\n",
    "            for x, y in [(i+1, j), (i-1,j), (i, j+1), (i, j-1)]:\n",
    "                if 0<=x<m and 0<=y<n and grid[x][y]>grid[i][j]:\n",
    "                    res += dfs(x, y)\n",
    "            return res % mod\n",
    "        return sum(dfs(i, j) for i in range(m) for j in range(n)) % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache,cache\n",
    "from string import *\n",
    "from itertools import product\n",
    "from collections import defaultdict\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        mod = 1000000007\n",
    "        dx = [1,0,0,-1]\n",
    "        dy = [0,1,-1,0]\n",
    "        # to down \n",
    "        # to right\n",
    "        @cache\n",
    "        def f(x:int,y:int)->int:\n",
    "            \n",
    "            res = 1\n",
    "            for tx,ty in zip(dx,dy):\n",
    "                tx,ty = tx+x,ty+y\n",
    "                if tx>= 0 and tx < m and ty >= 0 and ty < n and grid[x][y] < grid[tx][ty]:\n",
    "                    res = (res + f(tx,ty)) % mod\n",
    "            return res\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = (ans + f(i,j)) % mod\n",
    "        return ans\n",
    "            \n",
    "\n",
    "s = Solution()\n",
    "s.countPaths([[1,1],[3,4]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache,cache\n",
    "from string import *\n",
    "from itertools import product\n",
    "from collections import defaultdict\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        mod = 1000000007\n",
    "        dx = [1,0,0,-1]\n",
    "        dy = [0,1,-1,0]\n",
    "        @cache\n",
    "        # f(x,y)表示从(x,y)出发所能走的路径总数\n",
    "        def f(x:int,y:int)->int:\n",
    "            \n",
    "            res = 1\n",
    "            for tx,ty in zip(dx,dy):\n",
    "                tx,ty = tx+x,ty+y\n",
    "                if tx>= 0 and tx < m and ty >= 0 and ty < n and grid[x][y] < grid[tx][ty]:\n",
    "                    res = (res + f(tx,ty)) % mod\n",
    "            return res\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = (ans + f(i,j)) % mod\n",
    "        return ans\n",
    "            \n",
    "\n",
    "s = Solution()\n",
    "s.countPaths([[1,1],[3,4]])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\r\n",
    "        mod = 10 ** 9 + 7\r\n",
    "        m, n = len(grid), len(grid[0]) \r\n",
    "        @ cache \r\n",
    "        def dfs(x, y):\r\n",
    "            res = 1\r\n",
    "            for nx, ny in (x + 1, y), (x, y + 1), (x - 1, y), (x, y - 1):\r\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] < grid[x][y]:\r\n",
    "                    res += dfs(nx, ny) \r\n",
    "            return res % mod \r\n",
    "        return sum(dfs(i, j) for i in range(m) for j in range(n)) % mod\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        directions = [[-1, 0], (0, -1), (1,0), (0, 1)]\n",
    "        MOD = 10**9+7\n",
    "        @cache\n",
    "        def dfs(x, y):\n",
    "            res = 1\n",
    "            for dx, dy in directions:\n",
    "                nx, ny = x+dx, y+dy\n",
    "                if 0<=nx<m and 0<=ny<n and grid[nx][ny]>grid[x][y]:\n",
    "                    res += dfs(nx, ny)\n",
    "            return res%MOD\n",
    "        return sum(dfs(i, j) for i in range(m) for j in range(n)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10**9+7\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        n,m = len(grid), len(grid[0])\n",
    "        dirs = [[1,0], [-1,0], [0,1],[0,-1]]\n",
    "        @cache\n",
    "        def f(x,y):\n",
    "            res = 1\n",
    "            for dx,dy in dirs:\n",
    "                nx ,ny = x+dx,y+dy\n",
    "                if nx<0 or ny<0 or nx>=n or ny>=m:\n",
    "                    continue\n",
    "                if grid[nx][ny] > grid[x][y]:\n",
    "                    res += f(nx,ny)\n",
    "            return res%mod\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                res += f(i,j)\n",
    "        return res%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "MOD = 1_000_000_007\n",
    "DIRS = {(1, 0), (0, 1), (-1, 0), (0, -1)}\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        @cache\n",
    "        def dfs(x: int, y: int) -> int:\n",
    "            res = 1\n",
    "            for dx, dy in DIRS:\n",
    "                nx, ny = x + dx, y + dy\n",
    "                if (0 <= nx < m and \n",
    "                    0 <= ny < n and \n",
    "                    grid[nx][ny] > grid[x][y]):\n",
    "                    res = (res + dfs(nx, ny)) % MOD\n",
    "\n",
    "            return res\n",
    "\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = (res + dfs(i, j)) % MOD\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        MOD = 10**9 + 7\n",
    "        @cache\n",
    "        def dfs(i,j):\n",
    "            ans = 1\n",
    "            for x,y in (1,0),(-1,0),(0,1),(0,-1):\n",
    "                if 0 <= x + i < m and 0 <= y + j < n and grid[x + i][y + j] > grid[i][j]:\n",
    "                    ans += dfs(i + x,j + y) % MOD\n",
    "                    ans %= MOD\n",
    "            return ans\n",
    "\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans += dfs(i,j) % MOD\n",
    "                ans %= MOD\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):  # 从(i,j)出发有多少条strictly increasing path\n",
    "            res = 1  # only (i,j) itself\n",
    "            for dx, dy in dirs:\n",
    "                ni, nj = i + dx, j + dy\n",
    "                if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] > grid[i][j]:\n",
    "                    res += dfs(ni, nj)\n",
    "            return res\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dirs = [[0, 1], [1, 0], [0, -1], [-1, 0]]\n",
    "        return sum(dfs(i, j) for i in range(m) for j in range(n)) % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, grid, x, y, point_to_num_path):\n",
    "        if point_to_num_path[y][x] > 0:\n",
    "            return point_to_num_path[y][x]\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        npoints = 1\n",
    "        if x - 1 >= 0 and grid[y][x-1] > grid[y][x]:\n",
    "            npoints += self.dfs(grid, x-1, y, point_to_num_path)\n",
    "        if x + 1 < n and grid[y][x+1] > grid[y][x]:\n",
    "            npoints += self.dfs(grid, x+1, y, point_to_num_path)\n",
    "        if y - 1 >= 0 and grid[y-1][x] > grid[y][x]:\n",
    "            npoints += self.dfs(grid, x, y-1, point_to_num_path)\n",
    "        if y + 1 < m and grid[y+1][x] > grid[y][x]:\n",
    "            npoints += self.dfs(grid, x, y+1, point_to_num_path)\n",
    "        npoints = int(npoints % (10**9 + 7))\n",
    "        \n",
    "        point_to_num_path[y][x] = npoints\n",
    "        return npoints\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        point_to_num_path = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for y in range(m):\n",
    "            for x in range(n):\n",
    "                npoints = self.dfs(grid, x, y, point_to_num_path)\n",
    "        \n",
    "        res = 0\n",
    "        modn = 10 ** 9 + 7\n",
    "        for i in point_to_num_path:\n",
    "            res = int((int(sum(i) % modn) + int(res % modn)) % modn)\n",
    "\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import queue\n",
    "\n",
    "class Solution:\n",
    "    def dfs(self, grid, x, y, point_to_num_path):\n",
    "        if point_to_num_path[y][x] > 0:\n",
    "            return point_to_num_path[y][x]\n",
    "\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        npoints = 1\n",
    "        if x - 1 >= 0 and grid[y][x-1] > grid[y][x]:\n",
    "            npoints += self.dfs(grid, x-1, y, point_to_num_path)\n",
    "        if x + 1 < n and grid[y][x+1] > grid[y][x]:\n",
    "            npoints += self.dfs(grid, x+1, y, point_to_num_path)\n",
    "        if y - 1 >= 0 and grid[y-1][x] > grid[y][x]:\n",
    "            npoints += self.dfs(grid, x, y-1, point_to_num_path)\n",
    "        if y + 1 < m and grid[y+1][x] > grid[y][x]:\n",
    "            npoints += self.dfs(grid, x, y+1, point_to_num_path)\n",
    "        npoints = int(npoints % (10**9 + 7))\n",
    "        \n",
    "        point_to_num_path[y][x] = npoints\n",
    "        return npoints\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        point_to_num_path = [[0 for _ in range(n)] for _ in range(m)]\n",
    "        for y in range(m):\n",
    "            for x in range(n):\n",
    "                npoints = self.dfs(grid, x, y, point_to_num_path)\n",
    "        \n",
    "        res = 0\n",
    "        modn = 10 ** 9 + 7\n",
    "        for i in point_to_num_path:\n",
    "            res = int(int(sum(i) + res ) % modn)\n",
    "\n",
    "\n",
    "        return res\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        Mod = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        m1, n1 = m - 1, n - 1\n",
    "\n",
    "        @cache\n",
    "        def dp(r: int, c: int) -> int:\n",
    "            count = 1\n",
    "            row = grid[r]\n",
    "            v = row[c]\n",
    "            if r > 0 and grid[r-1][c] < v:\n",
    "                count += dp(r-1, c)\n",
    "            if r < m1 and grid[r+1][c] < v:\n",
    "                count += dp(r+1, c)\n",
    "            if c > 0 and row[c-1] < v:\n",
    "                count += dp(r, c-1)\n",
    "            if c < n1 and row[c+1] < v:\n",
    "                count += dp(r, c+1)\n",
    "            return count % Mod\n",
    "\n",
    "        return sum(dp(r, c) for r in range(m) for c in range(n)) % Mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        d=[[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        mod=10**9+7\n",
    "        @cache \n",
    "        def dfs(x,y):\n",
    "            if x<0 or y<0 or x>=m or y>=n:\n",
    "                return 0\n",
    "            ret=1\n",
    "            for a,b in d:\n",
    "                xx,yy=x+a,y+b\n",
    "                if 0<=xx<m and 0<=yy<n:\n",
    "                    if grid[x][y]>grid[xx][yy]:\n",
    "                        ret+=dfs(x+a,y+b)\n",
    "                        ret%=mod\n",
    "            return ret\n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans+=dfs(i,j)\n",
    "                ans%=mod\n",
    "        return ans "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        count = [[0] * n for i in range(m)]\n",
    "        steps = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        mod = int(1e9 + 7)\n",
    "        def dfs(i, j):\n",
    "            if count[i][j] > 0: return\n",
    "            c = 1\n",
    "            for i_, j_ in steps:\n",
    "                ii, jj = i + i_, j + j_\n",
    "                if ii >= 0 and ii < m and jj >= 0 and jj < n and grid[i][j] < grid[ii][jj]:\n",
    "                    dfs(ii, jj)\n",
    "                    c = (c + count[ii][jj]) % mod\n",
    "            count[i][j] = c\n",
    "            return\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dfs(i, j)\n",
    "                ans = (ans + count[i][j]) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        MOD = 1000000007\n",
    "        dx = [-1, 0, 1, 0]\n",
    "        dy = [0, 1, 0, -1]\n",
    "\n",
    "        @cache\n",
    "        def f(x: int, y: int) -> int:\n",
    "            ans = 1\n",
    "            for i in range(4):\n",
    "                nx, ny = x + dx[i], y + dy[i]\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[x][y] < grid[nx][ny]:\n",
    "                    ans = (ans + f(nx, ny)) % MOD\n",
    "            return ans\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                res = (res + f(i, j)) % MOD\n",
    "        return res   "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        count, visited = [[0] * n for i in range(m)], [[0] * n for i in range(m)]\n",
    "        steps = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        mod = int(1e9 + 7)\n",
    "        def dfs(i, j):\n",
    "            if visited[i][j] > 0: return\n",
    "            c = 1\n",
    "            for i_, j_ in steps:\n",
    "                ii, jj = i + i_, j + j_\n",
    "                if ii >= 0 and ii < m and jj >= 0 and jj < n and grid[i][j] < grid[ii][jj]:\n",
    "                    dfs(ii, jj)\n",
    "                    c = (c + count[ii][jj]) % mod\n",
    "            count[i][j] = c\n",
    "            visited[i][j] = 1\n",
    "            return\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dfs(i, j)\n",
    "                ans = (ans + count[i][j]) % mod\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        store = []\n",
    "        for i in range(m):\n",
    "            temp = []\n",
    "            for j in range(n):\n",
    "                temp.append(None)\n",
    "            store.append(temp)\n",
    "        def dfs(y, x, grid, store, m, n) -> int:\n",
    "            if store[y][x] is not None:\n",
    "                return store[y][x]\n",
    "            temp_1, temp_2, temp_3, temp_4 = 0, 0, 0, 0\n",
    "            if x + 1 < n:\n",
    "                if grid[y][x + 1] > grid[y][x]:\n",
    "                    temp_1 = dfs(y, x + 1, grid, store, m, n)\n",
    "            if x - 1 >= 0:\n",
    "                if grid[y][x - 1] > grid[y][x]:\n",
    "                    temp_2 = dfs(y, x - 1, grid, store, m, n)\n",
    "            if y + 1 < m:\n",
    "                if grid[y + 1][x] > grid[y][x]:\n",
    "                    temp_3 = dfs(y + 1, x, grid, store, m, n)\n",
    "            if y - 1 >= 0:\n",
    "                if grid[y - 1][x] > grid[y][x]:\n",
    "                    temp_4 = dfs(y - 1, x, grid, store, m, n)\n",
    "            store[y][x] = temp_1 + temp_2 + temp_3 + temp_4 + 1\n",
    "            return temp_1 + temp_2 + temp_3 + temp_4 + 1\n",
    "        res = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                num = dfs(i, j, grid, store, m, n)\n",
    "                res += num\n",
    "        return res % (10 ** 9 + 7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        dire = [[0,1],[0,-1],[1,0],[-1,0]]\n",
    "        MOD=1e9+7\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        @cache\n",
    "        def dfs(i,j)->int:\n",
    "            res=1\n",
    "            for d in dire:\n",
    "                x=i+d[0]\n",
    "                y=j+d[1]\n",
    "                if x>=0 and x<m and y>=0 and y<n and grid[i][j]>grid[x][y]:\n",
    "                    res+=dfs(x,y)\n",
    "                    res%=MOD\n",
    "            return res\n",
    "        \n",
    "        ans=0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans+=dfs(i,j)\n",
    "                ans %=MOD\n",
    "\n",
    "        return int(ans)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        rows = len(grid)\n",
    "        columns = len(grid[0])\n",
    "        longest_increasing_path_matrix = [0] * rows\n",
    "        for index in range(rows):\n",
    "            longest_increasing_path_matrix[index] = [0] * columns\n",
    "        answer = 0\n",
    "        for row in range(rows):\n",
    "            for column in range(columns):\n",
    "                answer += dfs(grid, longest_increasing_path_matrix, rows, columns, row, column, -1)\n",
    "        return answer % (10 ** 9 + 7)\n",
    "\n",
    "def dfs(grid, longest_increasing_path_matrix, rows, columns, row, column, pre_val):\n",
    "    if row < 0 or row >= rows or column < 0 or column >= columns or pre_val >= grid[row][column]:\n",
    "        return 0\n",
    "    if longest_increasing_path_matrix[row][column]:\n",
    "        return longest_increasing_path_matrix[row][column]\n",
    "    dy = [0, -1, 0, 1]\n",
    "    dx = [1, 0, -1, 0]\n",
    "    for index in range(4):\n",
    "        longest_increasing_path_matrix[row][column] += dfs(grid, longest_increasing_path_matrix, rows, columns, row + dy[index], column + dx[index], grid[row][column]) \n",
    "    longest_increasing_path_matrix[row][column] += 1\n",
    "    return longest_increasing_path_matrix[row][column]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        MOD = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(x: int, y: int) -> int:\n",
    "            res = 1\n",
    "            for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):\n",
    "                if (0 <= x + dx < m and 0 <= y + dy < n) and grid[x + dx][y + dy] < grid[x][y]:\n",
    "                    res += dfs(x + dx, y + dy)\n",
    "            return res\n",
    "        return sum(dfs(i, j) for i in range(m) for j in range(n)) % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, matrix: List[List[int]]) -> int:\n",
    "        R, C, res = len(matrix), len(matrix[0]), 0\n",
    "        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]\n",
    "        mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(r, c):\n",
    "            res = 1\n",
    "            for dr, dc in directions:\n",
    "                row, col = dr + r, dc + c \n",
    "                if 0 <= row < R and 0 <= col < C and matrix[row][col] > matrix[r][c]:\n",
    "                    res += dfs(row, col)\n",
    "            return res % mod\n",
    "        \n",
    "        for r in range(R):\n",
    "            for c in range(C):\n",
    "                res += dfs(r, c)\n",
    "        return res % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countPaths(self, grid: List[List[int]]) -> int:\n",
    "        directions = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        def in_grid(i: int, j: int):\n",
    "            return i >= 0 and i < m and j >= 0 and j < n\n",
    "        \n",
    "        MOD = 10 ** 9 + 7\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j):\n",
    "            res = 1\n",
    "            for d in directions:\n",
    "                x, y = i + d[0], j + d[1]\n",
    "                if in_grid(x, y) and grid[i][j] < grid[x][y]:\n",
    "                    res += dfs(x, y)\n",
    "            return res % MOD\n",
    "        ans = 0\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                ans = (ans + dfs(i, j)) % MOD\n",
    "        return ans"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
